package com.datastructure.test.findorder;

import java.util.*;

public class FindOrder {

    public static void main(String[] args) {
        FindOrder findOrder = new FindOrder();
        ArrayList<ArrayList<Integer>> groups = new ArrayList<>();
        ArrayList<Integer> group = new ArrayList<>();
        group.add(1);
        group.add(0);
        ArrayList<Integer> group1 = new ArrayList<>();
        group1.add(0);
        group1.add(1);
        groups.add(group);
        groups.add(group1);
        ArrayList<Integer> order = findOrder.findOrder(3, groups);
        System.out.println(order);
    }

    public int[] findOrder (int[][] prerequisites, int n) {
        // write code here
        HashSet<Integer> set = new HashSet<>();
        int max = 0;
        for (int[] prerequisite : prerequisites) {
            if (set.contains(prerequisites[0]) || set.contains(prerequisites[1])) {
                return new int[]{};
            }
            set.add(prerequisite[0]);
            set.add(prerequisite[1]);
            if (prerequisite[0] > max) {
                max = prerequisite[0];
            }
            if (prerequisite[1] > max) {
                max = prerequisite[1];
            }
        }
        while(set.size() < n){
            set.add(++max);
        }
        int[] res = new int[n];
        int i = 0;
        for(Integer v : set){
            res[i++] = v;
            if(i > n){
                break;
            }
        }
        return res;
    }

    public ArrayList<Integer> findOrder (int numProject, ArrayList<ArrayList<Integer>> groups) {
        // write code here
        int[][] prerequisites = new int[groups.size()][2];
        ArrayList<Integer> group;
        for (int i = 0; i < groups.size(); i++) {
            group = groups.get(i);
            prerequisites[i][0]=group.get(0);
            prerequisites[i][1]=group.get(1);
        }
        HashSet<Integer> set = new HashSet<>();
        int max = 0;
        for (int[] prerequisite : prerequisites) {
            if (set.contains(prerequisites[0]) || set.contains(prerequisites[1])) {
                return new ArrayList<>();
            }
            set.add(prerequisite[0]);
            set.add(prerequisite[1]);
            if (prerequisite[0] > max) {
                max = prerequisite[0];
            }
            if (prerequisite[1] > max) {
                max = prerequisite[1];
            }
        }
        while(set.size() < numProject){
            set.add(++max);
        }
        group = new ArrayList<>(set);
        return group;
    }
}
